in this video we're going to create a
quadrant system in unity ECS a quadrant
system helps us group nearby units into
quadrants that allows for massive
performance for any algorithm that
requires finding the neighbors since we
don't need to cycle through every single
entity but rather only the ones nearby
let's begin
[Music]
hello and welcome I'm your code monkey
and this channel is all about helping
you learn how to make your own games
with nf2 torrents made by a professional
indie game developer so if you find the
video helpful consider subscribing so
for here we have the final system that
we're going to create I've turned on
debug line so we can visually see each
quadrant as you can see when I press the
mouse over the world is clearly split
into separate quadrants there are units
and targets being spawned all over a
very massive area and all of those units
are searching for their closest target
now without using the equipment system
where we have 10,000 units independent
we looking for 10,000 targets you can
see that we are taking 56 milliseconds
per frame
however with enabling the equipment
system which ensures that the units only
look for targets nearby by enabling we
go down from 56 all the way down to 14
milliseconds so essentially a unit on
way over here will never even search for
a target all the way in here so you can
see the massive performance benefits of
using such a system especially when you
have on a lot of Units spread out over a
very large area now in here I am
demonstrating a fine target algorithm as
a way to view the benefits of a quadrant
system but it can really be applied to
any sort of problem the way the system
works is by first placing the units and
targets into their quadrant based on
their position then for each unit we
search the nearby quadrants for targets
and only those in the nearby quadrants
so this unit in here will search the
nearby quadrants but will never test the
position of the target all the way over
here so that's exactly what we want
since if the target is too far ignoring
it only makes sense for performance then
when the unit finds a college target it
simply has a component which moves it
towards the target and destroys it and
as you can see all the units in this
massive world they're all looking for
targets moving and destroying and in
here with 10,000 units looking for
10,000 targets we are getting some very
good performance alright so this circle
let's get to it so here is our starting
scene now this starting scene here is
the scene from the find causes target
video that we did previously so if you
haven't already go check out that video
again I'm only using the fine target as
an example algorithm this is just one of
the possible use cases for the quadrant
system it can be used to some of many
other Pro
that require knowing nearby entities
like for example obstacle avoidance
essentially we have units and targets
being spawned and the units are looking
for the targets however right now they
are currently looking for every single
target regardless of how far it is so
this unit down here is cycling through
all of the targets all the way up here
this is obviously very inefficient we
should only meet our cycles as much as
possible and only cycle through targets
that are actual potential targets so
let's see the code for how all of this
is set up here is our main script again
the starting point here is from the fine
target video so you can see that to see
how we got here from scratch we have
essentially two archetypes want to spawn
a unit and want to spawn a target they
are differentiated by these two tag
components which you can see down here
they are placed randomly and then we
spawn a bunch on the start and a bunch
every so often then we have the fine
turret system this one has a bunch of
jobs to cycle through each target and
find it closest when he does find the
closest target he adds the hands target
component with the target entity this
component only holds the target entity
and then we have this system right here
which runs on entities that have a
target and simply moves them towards the
target alright so this is our basic set
up now let's begin writing the code for
our quadrant system so in here let's
start off by making a new C sharp script
for our quadrant system now in here get
rid of this and instead of a mono
behavior this will be a component system
now in here we're going to have a bunch
of jobs to place our entities into their
respective quadrant
but first let's think of how we're
actually going to store a quadrant we
need some way to have multiple values
for a single quadrant so for that we can
use a negative multi hash map this
collection lets us have multiple values
per single key so that's great now all
we need is a way to get a key for each
quadrant
now there are many ways to count like
keys to put positions in various buckets
let's pick one that returns just a
simple int so our multi hash map won't
be composed of keys based on an in
and it will home entities so let's make
a function to calculate the quadrant you
need to make this a private static it
won't return an int and let's call it
get position hash map key in here will
receive a full three for the position
and we want to return the hash map key
related to this position so in here
we're just going to use some simple math
in order to create some very simple
squares all right so here we have a
simple function essentially we are
flooring the X and the y based on a
certain quadrant cell size and for the Y
we are simply multiplying by a certain
value so for example an entity on 0 0
will have a key of 0 however an entity
on 60 0 will have a key of 1 so this
function will essentially convert our
position into a nice hash map key now in
order to visually see this let's make a
nice debug function to draw each
quadrant
okay so here it is
now all we're doing is essentially just
drawing four lines in order to draw a
square for our quadrant so we complete
the lower left vector which is doing the
exact same math as up here we just do a
floor on the X and the y and then you
draw a line from your lower left into
the on lower right then on the upper
left and so on and so on
so now let's test this down here on our
update let's draw it on the mouse
position so a debug drop quadrant now in
here let's draw it on the mouse position
so for that I'm going to use a function
from the code monkey utilities that you
can grab for free from unity code monkey
calm so using code monkey dot utils and
then simply use the you tells class to
get the monitor on position okay so just
like that we should be able to see all
of our quadrants okay so here we are now
first of all since we're using the debug
drawn line we need to go up here in
order to enable gizmos and now in here
on this scene we are using a very small
camera size so let's modify our quadrant
size in here instead of setting the
quadrant son size at 50 and let's just
put in that five so here you can already
see the quadrants being drawn let's zoom
out a bit and there it is okay so this
is one quadrant as you can see and as I
reach the edge there's another quadrant
and in there another another and down
here you can see the values that aren't
automatically completed so this one has
the quadrant hash key of 0 this one a
hash key of one and two and this one is
0 and above it is a thousand done - a
thousand so essentially we have a nice
unique hash key for each position in our
map so just like that we have separated
our entire world into various quadrants
now what we need to do is actually put
these objects into the quadrant that
they've done so for example this unit
here would be on this quadrant now this
one now this one and so on so in order
to place our entities into quadrants
let's start off by making this very
simple and using simple single thread
code which will later convert into jobs
so in here and let's simply cycle
through all entities and grab their
position
so with translation we can get the
position hashmap team and we pass in the
translation value so we calculate the
hashmap key based on the position of
this entity and now we simply add it to
the hashmap so before let's instantiate
our hash map so we create a new one now
in here we need a capacity in this case
we're going to fill it up with all of
our entities so let's calculate how many
entities we have so we calculate the in
length and then we create it using a
locator that temp job and in here we
simply go into our hash map in order to
add passing our hash map King and let's
store the entity and that's it we now
have our entities being correctly placed
into their specific quadrant now to make
sure that this is working correctly
let's make a function to count how many
entities are in a single quadrant so
let's make a private static int call it
gift entity count and hash map now in
here we'll receive our native multi hash
map then we also receive an int for our
hash map key so we want to return how
many entities are inside this key now in
order to get the values from the multi
hash map we need to use the multi hash
map duct try get first value so this one
receives a keys or hash map key then we
need to pass in a variable which will be
the out parameter for our entity so it
has out entity into that variable then
we also need a native multi hash map
iterator
and just like that now this returns a
boolean if we have a first value inside
this hashmap team so if we do have the
first value let's test if there are more
values so in here let's do a cycle a
do-while so we're going to do something
while we still have values so in order
to test we do a try and get the next
value and here we pass in the same out
for our entity and it reference to the
same native multi hashmap iterate so
this cycle won't keep running for as
long as there's entities inside the same
hashmap key so here we can just simply
define it for our count start off at
zero and here increases and out here we
return alright so we have a nice simple
function cycling through all the values
inside our hash map and returns the
correct total so this is how you iterate
through a native multi hash map
essentially you try to get the first
value and then keep getting the next
value until there are no more all right
so let's test this out down here let's
still draw our quadrant and then let's
do a debug log of our account then we
get the position hash map key of the
current Mouse world position so we
should be able to see in the log how
many entities are stored in the quadrant
right beneath the mouse then here since
we're dealing with a native multi hash
trap we need to make sure to dispose of
it in the end
ok so let's test ok so here we are and
let's see if it is correct we can
already see the current quadrant being
highlighted so this one and then this
one so now let's go to the left and here
on the wall we are seeing two and indeed
we have one and two entities now I see
this quadrant down here and we have four
and yep one two three four and in here
we have one two three and yep exactly
correct all right awesome so we have
successfully created the quadrant system
to place our entities into various
buckets now that we have this code work
let's improve upon it so the first thing
is obviously convert this into a job so
let's go up here in r2
a struct let's call it the set quadrant
data hash map job so we're going to set
the data for each pattern and it's going
to be an eye job for each with entity
and we also want the translation now in
here we need to receive the native multi
hash map and since in this job we are
going to be assigning values into our
hash map we need to pass in the dot
concurrent in order to be able to
concurrently write to the same hash map
now on execute we're going to do the
same thing we were doing down here
we currently the hash map key based on a
translation and then we simply add it
into that key this entity so that's it
as you can see very simple and finally
we can just very easily add the first
component in order to make this even
faster so now down here instead of doing
our for each let's create our job all we
need to do is pass in our quadrant multi
hash map make sure you write two
concurrent and in here we can schedule
our job alright so that's pretty much it
our code should still be working exactly
the same as previously however right now
we are benefiting from multi-threaded
code
yt and if there is everything still
works normal this quadrant has need two
entities this one only one and yep
everything is written correct let's see
just how quickly this cheiron's
so let's disable our debug and spawn on
what more units okay so here we have a
thousand units and a thousand Terry it's
being spawned and if we check out the
stats you can see that all of them are
being placed in the correct buckets into
their native multi hash map and as you
can see the whole thing is only taking
one millisecond so thanks using jobs
this system is insanely fast ok so now
right now we are only storing the entity
that works but if we need more info from
that entity we're going to have to do an
expensive column going into the entity
manager in order to get the component
data and so on so we should really find
a way to store more than just the entity
into our quadrants so here in our
quadrant system instead of having
a native multi hashmap of entities let's
go up here in order to define a very
simple struct let's make a struct and
call it pardon that I mean here let's
start off by simply our entity and now
we modify all of our function columns in
order to work with a multi hash map of
quadrant data so in here when adding we
need to create a new quadrant data in
this case we just constantly entry
alright so we now have our native multi
hash map working with a specific struct
so we can go up here and add as many
balances we need in order to work with
our coordinate system so for example
let's add a whole 3 for the position so
down here when we add it let's also add
the position which is a translation that
though so just like that we have made
our code more robust by making it work
with a specific struct inside of the
entity so this way we can clearly define
what that we're going to need for our
quadrant system so let's run the code
just make sure everything still works
any of everything is still working and
it's still working insanely fast now
another improvement we can do is to only
play certain entities into our quadrants
so right now we're running this query
which is simply searching for entities
with translation so any entity we create
as long as it has a translation it's
being added into the quadrant system
that can be quite wasteful if you have
bunch of entities that are not intended
to be used by the equipment system like
for example if you have entities for a
particle system so let's make a very
simple component to define which
entities should be placed so we can go
up here in order to simply make a struct
for a component let's call it private
entity so we're only going to work with
entities that have this component now an
empty component works perfectly fine
however we can also set more information
in here so for example we can store a
type
so here we're defining two types a unit
and a target and we're storing that on
our quadrant entity so let's go to when
we are in Senshi ating our archetypes in
here we also add the type of quadrant
entity in order to make sure it gets
added into our quadrant system then we
set the component data just like that so
we add our component in order to be used
by the quantity system and we passing
the information that is needed and now
in here on our quadrant data we can also
store a quadrant entity so all we're
doing is adding all the information
we're going to need in order to be
stored for each entry into our quadrant
system so down here when we add our key
let's this as well okay so now our set
data job now receives a quadrant entity
which we're going to use in order to add
to the hashmap key now down here our
antiquary is no longer just a
translation but translation and the type
of quadrant entity alright so that
should do it
so we can now add this component to any
entities that we want to be used by this
quadrant system and we have a lot more
information being stored for each entry
into each quadrant let's see and yep
everything's still working perfectly
fine and it's still pretty fast so again
everything still works but we can now
easily define which entities should be
placed in quadrants and which should be
ignored
now another improvement we can make is
regarding the native multi hash map
field so right now we're creating and
disposing of it on every frame now this
works but obviously means we no longer
have our quadrants once the system is
done meaning if we want to use this
quadrant system by another script we
would have to add all of the related
code in here so for example our finite
area code would have to be placed right
here instead of being in its own
specific class so instead of doing that
let's make this a permanent
of multi hashmap so we can simply do it
over right on the uncreate now we're
going to create a native multi hash map
and we're going to define it as a static
variable so we have our static quadrant
hash map so that can be used by other
scripts down here we instantiate it very
much in the same way except for the
allocator we used persistent then let's
also override the on destroy in order to
make sure we dispose of it and now we no
longer need to do this in here okay so
let's run the code and see and just like
that we have an error right away this
tells us that our hash map is full
that's because the hash map cannot grow
dynamically inside a jar so we need to
make sure we give it the correct
capacity before running our jobs so in
here we need to expand it to fit so we
check if the entity query contantly the
link if that is bigger than the quadrant
capacity then let's expand it in order
to expand we just set the capacity to be
the new link and that's it just like
that our quadrant multi hash map will
now expand to fit whatever it needs and
since this is persistent we need to make
sure to clear it so before we do this
let's clear the current catchment all
right so let's try again any of here it
is in our code is working fine no errors
and everything still works okay awesome
so everything still works the same
except now we have our hash map which is
accessible from other systems so now
let's finally apply this to our fine
target code here is the fine target
system again this system was made in a
previous video so check that out to see
how it works so in here we are
essentially going through every single
target we have the fine target job which
in here cycles through every single
target and sees how far away it is now
let's do this by cycling through the
targets only in a single quadrant so
let's make a private stroke
fine target quadrant system why let's
copy-paste this target as our starting
point now in here we no longer receive
an array of targets or rather we're
going to receive our negative multi hash
map in here we calculate the hash map
key based on our translation then we
send on through the entities in that
hash map key so here we are cycling
through all the values inside this hash
map key so it's in here that we need to
find the target so use the families that
we stored in our quadrant and so we
store the entity and the position and
that's it so we have a very nice job
looking for targets but only looking
those that are in the same quadrant one
thing we also added in our quadrant data
was the quadrant entity so in this case
we only want targets that are of
different quadrant entity type so
essentially we're going to only search
for targets that have a different type
in them from this one so type gnomes are
the unit or the target so the units will
look for targets and if we want it we
could also make the targets look for
units all right so now let's replace our
job down here for the multi hash map we
can send the one that we have our
reference on our quadrant system
all right that should do it
let's test and we should now have units
looking for targets only in their
quadrant so let's see and yep they are
correctly finding their targets and
moving towards it and these right here
are static meaning they no longer have
targets inside their quadrant system so
you can see that they are only searching
for targets inside of their quadrant all
right so obviously it worked but you can
already see the issue right now the
turning range is limited by the quadrant
sighs so this target right here is
outside of the quadrant so these two
will not find it so this is a problem
with a lot of different solutions
depending on how fast or accurate you
want your targeting to be now in this
case we can simply increase the quadrant
size by a little bit and make sure our
unit search for nearby quadrants as well
so here let's put this code into a
function so we can easily check the
nearby quadrants
all right so here we have put our fine
target code into a separate function
you'll receive a hashmap key so we can
easily check the neighbors and let's
just make sure that this is still
working the same and you've okay
everything's still working the same look
at these two looking for targets and
they don't search for those and say are
far and yep exactly
okay everything's still working so now
in here we can easily check for all of
the neighbor problems so first we check
the one on the hashmap e so that's the
one that he's in then we check the one
to the right which is plus one on the
index then we check on the left so it
has a hashmap key of minus one then we
check above so it's Fosdick button
system that quadrant Y multiplier that's
the one above and the minus will be the
one below again this is all based on how
we calculated our hash map King now for
the corners so here we are searching for
all the targets in the neighboring
quadrants and here in our quadrant
system let's also increase the sound
size by a little bit okay let's test and
okay here we are and all our units are
searching for targets and as you can see
they are searching for nearby quadrants
look at that one so for example that one
finishes those three targets another
getting searched for the ones on the
quadrant next to it all right so our
units are now looking for targets on
more than just their quadrant so the
targeting is now a lot more accurate and
as you can see our frame rate is still
pretty much the same only taking one
milliseconds so now let's see exactly
just how fast this is let's make sure
they keep on looking for targets so
let's stop adding the component in the
end so our add component job let's not
add a component that way they're gonna
constantly keep looking for targets and
let's modify the code noir to enable to
test both methods so here we have 10,000
units being spawned over a massive area
along with 10,000 targets
and as you can see it is taking 70
milliseconds in order to find the causes
so every single one of those 10,000
units is cycling through every single
one of those 10,000 targets so obviously
that is very wasteful since a unit
here doesn't care about a target on the
way over here so now let's enable the
quadrant system and there you go we went
down from 6e all the way down to 15
milliseconds so right now this unit down
here doesn't care and doesn't even try
to search for this target over here so
the units are only searching for targets
in their quadrant and the ones nearby
now again the fine target is just one
possible use for the quadrant system the
whole point is placing entities into
smaller separate buckets that way you
have much faster searching for whatever
it is you want to do that relates to
entity positions for example you can
make a unit avoidance algorithm just
search for the closest entity in the
quadrant and see if it is close enough
and if so stop moving the possibilities
are endless and this is a great system
to apply to many different problems as
always you can download the project
files in utilities from Unity code
monkey comm if you liked the video
subscribe channel for more ent tutorials
post any questions you have in the
comments and I'll do my best interval
alright see you next time
[Music]